import { FARule } from "./dfa";

export class NFARuleBook {
    constructor(
        public rules:FARule[] = []
    ){}

    next_states(states:symbol[],character:string){
        let next_states:symbol[] = [];
        states.forEach(state => {
            next_states = next_states.concat(
                this.follow_rules_for(state,character)
            )
        })
        return Array.from(new Set(next_states));
    }

    follow_rules_for(state:symbol,character:string){
        return this.rules_for(state,character).map(rule => rule.follow())
    }
    rules_for(state:symbol,character:string):FARule[]{
        let nextRule:FARule[] = [];
        this.rules.forEach(rule => {
            if(rule.applies_to(state,character)){
                nextRule.push(rule);
            }
        })
        return nextRule
    }
    // 自由移动后的所有状态可能
    follow_free_moves(states:symbol[]){
        let more_states = this.next_states(states,"");
        let checkAll = true;
        for (let index = 0; index < more_states.length; index++) {
            const state = more_states[index];
            if(!states.includes(state)){
                checkAll = false;
                break
            }
        }
        if(!checkAll){
            states = states.concat(more_states)
            this.follow_free_moves(states)
        }
        return states
    }
}
export class NFA {
    constructor(
        public current_states:symbol[],
        public accept_states:symbol[],
        public rulebook:NFARuleBook
    ){
        this.current_states = this.rulebook.follow_free_moves(this.current_states)
    }
    accepting(){
        //获取交集
        let acceptState:symbol[] = [];
        this.current_states.forEach(state => {
            if(this.accept_states.indexOf(state) > -1){
                acceptState.push(state)
            }
        })
        return acceptState.length > 0
    }

    read_character(character:string){
        this.current_states = this.rulebook.next_states(this.current_states,character)
        //计算可自由移动
        this.current_states = this.rulebook.follow_free_moves(this.current_states)
    }

    read_string(input:string){
        let inputArray = input.split('');
        inputArray.forEach(i => {
            this.read_character(i)
        })
    }
}

export class NFADesign{
    constructor(
        public start_state:symbol,
        public accept_states:symbol[],
        public rulebook:NFARuleBook
    ){}

    to_nfa(){
        return new NFA([this.start_state],this.accept_states,this.rulebook)
    }
    accepts(input:string){
        let nfa = this.to_nfa()
        nfa.read_string(input)
        return nfa.accepting()
    }

}
// 每个输入,转换的状态多种可能性()
// 多种起始状态 
// 读取输入(读取空输入 自由移动实现或关系)
// 下一个可能状态
// let rulebook = new NFARuleBook([
//     new FARule(1,'a',1),
//     new FARule(1,'b',1),
//     new FARule(1,'b',2),

//     new FARule(2,'a',3),
//     new FARule(2,'b',3),

//     new FARule(3,'a',4),
//     new FARule(3,'b',4)
// ])
// console.log(rulebook.next_states([1],'b'))
// console.log(rulebook.next_states([1,2],'a'))
// console.log(rulebook.next_states([1,3],'b'))

// console.log(new NFA([1],[4],rulebook).accepting()) 
// console.log(new NFA([1,2,4],[4],rulebook).accepting()) 


// let nfa = new NFA([1],[4],rulebook)
// console.log(nfa.accepting())
// nfa.read_character('b')
// console.log(nfa.accepting())
// nfa.read_character('a')
// console.log(nfa.accepting())
// nfa.read_character('b')
// console.log(nfa.accepting())

// nfa.read_string('bbbb')
// console.log(nfa.accepting())

// let nfa_design = new NFADesign(1,[4],rulebook)
// console.log(nfa_design.accepts('bab'))
// console.log(nfa_design.accepts('bbbbb'))
// console.log(nfa_design.accepts('bbabb'))


// let rulebook2 = new NFARuleBook([
//     new FARule(1,"",2),
//     new FARule(1,"",4),

//     new FARule(2,'a',3),
//     new FARule(3,'a',2),

//     new FARule(4,'a',5),
//     new FARule(5,'a',6),
//     new FARule(6,'a',4),
// ])

// console.log(rulebook2.next_states([1],''))
// console.log(rulebook2.follow_free_moves([1]))

// let nfa_design = new NFADesign(1,[2,4],rulebook2)
// console.log(nfa_design.to_nfa().current_states)
// console.log(nfa_design.accepts('aa'))
// console.log(nfa_design.accepts('aaa'))
// console.log(nfa_design.accepts('aaaaa'))
// console.log(nfa_design.accepts('aaaaaa'))

